package com.yun.datastructure.linear.list.linkedlist.leetcode;

import com.yun.datastructure.linear.list.linkedlist.ListNode;

public class Leetcode206 {
    /*
        方法1：构造一个新链表，从旧链表依次拿到每个节点，创建新节点添加到新链表的头部，完成后的新链表即是倒叙的
        优点：简单直白
        缺点：需要创建新节点，占用空间
     */
    public ListNode reverseList1(ListNode head) {
        ListNode n1 = null;
        ListNode p = head;
        while (p != null) {
            n1 = new ListNode(p.val, n1);
            p = p.next;
        }
        return n1;
    }

    /*
        方法2：构造一个新链表，从旧链表头部移除节点，添加到新链表的头部，完成后的新链表即是倒叙的
            和方法1区别在于不用创建新的节点但是需要自己写一个外部的容器类
        优点：真正写代码的时候会这样写，这是一种面向对线的思维方式
     */
    public ListNode reverseList2(ListNode head) {
        List list1 = new List(head);
        List list2 = new List(null);
        while (true) {
            ListNode first = list1.removeFirst();
            if (first == null) {
                break;
            }
            list2.addFirst(first);
        }
        return list2.head;
    }

    //方法2的集合工具类
    static class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        public void addFirst(ListNode first) {
            first.next = head;
            head = first;
        }

        public ListNode removeFirst() {
            ListNode first = head;
            if (first != null) {
                head = first.next;
            }
            return first;
        }
    }

    /*
        方法3：递归
        单向链表没有prev指针，但是利用递归的特性记住了链表倒过来的顺序
     */
    public ListNode reverseList3(ListNode p) {
        if (p == null || p.next == null) {
            return p;
        }
        ListNode last = reverseList3(p.next);
        p.next.next = p;
        p.next = null;
        return last;
    }

    /*
        方法4：
        n1
        o1
        1 ->2 ->3 ->4 ->5 ->null

        old1
        new1
     */
    public ListNode reverseList4(ListNode o1) {
        if (o1 == null || o1.next == null) {
            return o1;
        }
        ListNode o2 = o1.next;
        ListNode n1 = o1;
        while (o2 != null) {
            o1.next = o2.next;
            o2.next = n1;
            n1 = o2;
            o2 = o1.next;
        }
        return n1;
    }

    /*
        方法5：类似于方法2，但是方法5更加面向过程，方法2面向对象
        o1
        1 ->2 ->3 ->4 ->5 ->null

        n1
        null
     */
    public ListNode reverseList5(ListNode o1){
        if (o1 == null || o1.next == null) {
            return o1;
        }
        ListNode n1=null;
        while (o1 != null){
            ListNode o2=o1.next;
            o1.next=n1;
            n1=o1;
            o1=o2;
        }
        return n1;
    }

    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        System.out.println(o1);
        ListNode n1 = new Leetcode206().reverseList5(o1);
        System.out.println(n1);
    }
}
